package com.dq.offer;

import com.dq.utils.CreateArray;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/18  21:48
 * @Description:
 */
public class Arrive {
    public static void main(String[] args) {
        Solution solution = new Arrive().new Solution();
        int[][] connections = (int[][]) CreateArray.genIntArray("[[0,1],[1,3],[2,3],[4,0],[4,5]]");
        int n = 6;
        System.out.println(solution.minReorder(n, connections));
    }
    class Solution {

        public int minReorder(int n, int[][] connections) {

            int res = 0;
            int[][] matrix = new int[n][n];
            for(int i = 0; i < connections.length; i++){
                matrix[connections[i][0]][connections[i][1]] = 1;
                matrix[connections[i][1]][connections[i][0]] = -1;
            }
            boolean[] visit = new boolean[n];
            Deque<Integer> queue = new LinkedList<>();
            queue.offer(0);
            while(!queue.isEmpty()){
                int node = queue.poll();
                for(int j = 0; j < n; j++){
                    if(visit[j] || node==j || matrix[node][j]==0) continue;
                    if(matrix[node][j] == 1){
                        res++;
                    }
                    queue.offer(j);
                }
                visit[node] = true;
            }
            return res;

        }

    }
}
